package com.beimihu.leetcode;

public class Kmp {
    private static int[] getNext(String t) {
        int[] next = new int[t.length()];
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < t.length(); i++) {
            while (j > 0 && t.charAt(i)!= t.charAt(j)) {
                j = next[j - 1];
            }
            if (t.charAt(i) == t.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
    // 在s中查找t
    public static int strSTR(String s, String t) {
        if (t.isEmpty()) {
            return 0;
        }
        int[] next = getNext(t);
        int j = 0;
        for (int i = 0; i < s.length(); i++) {
            while (j > 0 && s.charAt(i)!= t.charAt(j)) {
                j = next[j - 1];
            }
            if (s.charAt(i) == t.charAt(j)) {
                j++;
            }
            if (j == t.length()) {
                return i - j + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String s = "ABABDABACDABABCABAB";
        String t = "ABAC";
        int result = strSTR(s, t);
        if (result!= -1) {
            System.out.println("模式串在文本串的第 " + (result + 1) + " 位置找到");
        } else {
            System.out.println("未找到匹配的模式串");
        }
    }
}
